1. Field of the Invention
The present invention relates to computer systems. More specifically, the present invention relates to a method and an apparatus for facilitating mark-sweep garbage collection with reference counting in a memory-management system.
2. Related Art
Computer users are demanding the ability to scale computer applications so that they can use very large heaps while maintaining a high level of performance. During computer system operation, an object within a heap becomes unreachable when it is no longer reachable from any process or thread. The unreachable object is then considered to be “garbage”. As time passes, a buildup of these garbage objects can slowly exhaust the memory space. The process of finding all the garbage objects and reclaiming the memory space that they occupy is referred to as “garbage collection”. Unfortunately, garbage collection of very large heaps can be a very time-consuming and costly process. As a result, system users are demanding lower garbage collection overhead and lower pause times for memory-management systems that perform garbage collection operations.
Commonly used garbage collection schemes are typically based on the mark-sweep technique. Mark-sweep garbage collection involves traversing and marking all reachable “live” objects in the heap, and then reclaiming (or “sweeping”) the unmarked garbage objects. Unfortunately, this technique may be inefficient in dealing with portions of the heap that are not frequently modified, such as a large read-mostly database. During each garbage collection cycle, all of the live objects are remarked even if that portion of the heap was not modified.
Alternatively, reference-counting garbage collection involves maintaining a reference count in each object of the number of other references in the heap which refer to the object. The reference count of an object is only updated when a reference is added to or removed from a referring object. When a reference count reaches zero, the object may be reclaimed. However, reference counting may be inefficient because, whenever a reference in the heap is modified, the reference counts on the old and new referents must be adjusted. This additional overhead may be prohibitively expensive when the contents of the heap are rapidly changing.
Hence, what is needed is a garbage collection system with the efficiency of mark-sweep garbage collection for portions of the heap which are frequently modified, and the efficiency of reference-counting garbage collection for portions of the heap which are not frequently modified.